子树|也就是_认识堆和堆排序

篇首语：本文由编程笔记#小编为大家整理，主要介绍了认识堆和堆排序相关的知识，希望对你有一定的参考价值。

10、堆

10.1、完全二叉树

10.2、大跟堆

在一个完全二叉树里&＃xff0c;每一颗子树的最大值就是头结点的值&＃xff0c;满足这个条件就是大跟堆。

10.3、小跟堆

在一个完全二叉树中&＃xff0c;每一颗子树的最小值就是他的头结点&＃xff0c;满足这个条件就是小跟堆。

怎么让一个完全二叉树变成大跟堆呢&＃xff1f;

一开始heapsize是为0的&＃xff0c;然后5进来的时候&＃xff0c;就放到heapsize为0的位置&＃xff0c;然后heapsize变为1了&＃xff0c;再进来一个数3的时候&＃xff0c;将其放到heapsize为1的位置&＃xff0c;然后heapsieze变为2&＃xff1b;在进来6的时候&＃xff0c;将其放到heapsize为2的位置&＃xff0c;heapsize变为3&＃xff1b;这时候根据父结点的寻找公式来确定子节点的父结点是啥&＃xff0c;所以6可以确定他的父结点是5&＃xff0c;这时候就要比较父结点跟子节点&＃xff0c;子节点要是比父结点大&＃xff0c;就得交换两者位置&＃xff0c;如果小的话就不用交换位置&＃xff0c;继续处理进来的另一个数。通过父结点的比较可以每次进来一个数都能将其调整为大跟堆的形式。

要将大跟堆中的最大值拿掉&＃xff0c;怎么让原本的大跟堆还保持大跟堆的状态。

大跟堆的头结点跟最后一个结点的值交换&＃xff0c;然后heapsize减小1&＃xff1b;heapsize减一之后就以为这之前的头结点也就是换到最后一个结点的值是不存在大跟堆了&＃xff0c;因为heapsize减一后如果还要最后一个结点就是下标越界了。

调换之后可能之前的大跟堆已经不再是大跟堆的结构了&＃xff0c;所以需要再次调整为大跟堆&＃xff0c;怎么调整呢&＃xff1f;

从头结点开始&＃xff0c;找他的子节点中的最大值&＃xff0c;然后最大值跟父结点交换。

问题&＃xff1a;如果现在要修改大跟堆中的i位置的某个值为其他的值&＃xff0c;那么怎么保证这个完全二叉树还是大跟堆呢&＃xff1f;

首先看他修改后的值跟之前的值比较&＃xff0c;如果比之前的大&＃xff0c;那么就跟上面的进行一个比较&＃xff0c;也就是headfy操作。如果比之前的小&＃xff0c;就跟下面的进行比较。

堆其实就是只有两个操作&＃xff0c;一个是heapsize操作一个是headfy操作。

package 左神算法.堆;
public class Heap
public static void main(String[] args)
int[] arr &＃61; 7, 3, 6, 5, 8;
int index &＃61; 4;
int heapSize &＃61; 0;
heapInsert(arr, index);
heapify(arr, index, heapSize);
for (int i &＃61; 0; i < arr.length; i&＃43;&＃43;)
System.out.print(arr[i] &＃43; " ");


//某个数现在处在index位置&＃xff0c;往上继续移动
public static void heapInsert(int[] arr, int index)
while (arr[index] > arr[(index - 1) / 2])
swap(arr, index, (index - 1) / 2);
index &＃61; (index - 1) / 2;


//某个数在index位置&＃xff0c;能否往下移动
public static void heapify(int[] arr, int index, int heapSize)
int left &＃61; index * 2 &＃43; 1;//左孩子的下标
while (left < heapSize) //下方还有孩子的时候
// 两个孩子中&＃xff0c;谁的值大&＃xff0c;把下标给largest
int largest &＃61; left &＃43; 1 < heapSize && arr[left &＃43; 1] > arr[left] ? left &＃43; 1 : left;
// 父和孩子之间&＃xff0c;谁的值大&＃xff0c;把下标给largest
largest &＃61; arr[largest] > arr[index] ? largest : index;
if (largest &＃61;&＃61; index)
break;

swap(arr, largest, index);
index &＃61; largest;
left &＃61; index * 2 &＃43; 1;


public static void swap(int[] arr, int i, int j)
int temp &＃61; arr[i];
arr[i] &＃61; arr[j];
arr[j] &＃61; temp;


/*
8 7 6 5 3
*/


时间复杂度&＃xff1a;O(logN)

11、堆排序

时间复杂度&＃xff1a;O(NlogN)

如果是给定了所有的元素在堆里面&＃xff0c;然后调整成大跟堆&＃xff0c;就可以先调整下面的然后继续往上。结果时间复杂度可以计算如下&＃xff1a;完全二叉树中的叶子结点是N/2;

11.1、堆排序扩展题目

假设k&＃61;6的时候&＃xff0c;数组中的0-6中的7个元素加入到小跟堆中&＃xff0c;因为k&＃61;6&＃xff0c;移动距离不能超过6&＃xff0c;所以将0-6位置的元素从小跟堆弹出&＃xff0c;然后再加入7后面的元素。最后数组中的元素都会从小跟堆弹出到一个数组中

时间复杂度O(N*logK)